package main

import "container/heap"

/**
 *
 * @param a int整型一维数组
 * @param n int整型
 * @param K int整型
 * @return int整型
 */
func findKth(a []int, n int, K int) int {
	// write code here
	h := NodeHeap{}
	heap.Init(&h)

	for i := 0; i < n; i++ {
		heap.Push(&h, a[i])
		for h.Len() > K {
			_ = heap.Pop(&h).(int)
		}
	}
	return heap.Pop(&h).(int)
}

// NodeHeap 大根堆
type NodeHeap []int

func (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
